<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Programming Concepts
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial005.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial007.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H1 CLASS="chapter"><A NAME="htoc42">Chapter&nbsp;5</A>&nbsp;&nbsp;Programming Concepts</H1><UL>
<LI><A HREF="tutorial006.html#toc19">Overview</A>
<LI><A HREF="tutorial006.html#toc20">Alternatives</A>
<LI><A HREF="tutorial006.html#toc21">Iteration on lists</A>
<LI><A HREF="tutorial006.html#toc22">Iteration on terms</A>
<LI><A HREF="tutorial006.html#toc23">Iteration on array</A>
<LI><A HREF="tutorial006.html#toc24">Transformation</A>
<LI><A HREF="tutorial006.html#toc25">Filter</A>
<LI><A HREF="tutorial006.html#toc26">Combine</A>
<LI><A HREF="tutorial006.html#toc27">Minimum</A>
<LI><A HREF="tutorial006.html#toc28">Best and rest</A>
<LI><A HREF="tutorial006.html#toc29">Sum</A>
<LI><A HREF="tutorial006.html#toc30">Merge</A>
<LI><A HREF="tutorial006.html#toc31">Group</A>
<LI><A HREF="tutorial006.html#toc32">Lookup</A>
<LI><A HREF="tutorial006.html#toc33">Fill matrix</A>
<LI><A HREF="tutorial006.html#toc34">Cartesian</A>
<LI><A HREF="tutorial006.html#toc35">Ordered pairs</A>
</UL>

<A NAME="programmingconcepts"></A>
<A NAME="toc19"></A>
<H2 CLASS="section"><A NAME="htoc43">5.1</A>&nbsp;&nbsp;Overview</H2>
In this chapter we will present typical programming concepts<A NAME="@default105"></A> in ECLiPSe with example 
uses in the RiskWise application. These programming concepts each perform one 
particular operation in an efficient way, and show how these tasks should be 
programmed in ECLiPSe. They can be adapted to specific tasks by adding 
additional parameters, changing calls inside the concepts or passing different 
data structures. <BR>
<BR>
The presentation of the concepts follows the same pattern: We first describe the 
concept in general terms and then present the parameters required. This is 
followed by one or several implementations of the concept in ECLiPSe, and 
some larger examples from the RiskWise code.<BR>
<BR>
<A NAME="toc20"></A>
<H2 CLASS="section"><A NAME="htoc44">5.2</A>&nbsp;&nbsp;Alternatives</H2>

<H5 CLASS="paragraph">Description</H5> This concept is used to choose between alternative <A NAME="@default106"></A>actions 
based on some data structure. For each alternative, a guard <I>q</I><SUB><I>i</I></SUB> is specified. 
The guard <A NAME="@default107"></A>is a test which succeeds if the condition for selecting one alternative 
is met. The actions <A NAME="@default108"></A><I>r</I><SUB><I>i</I></SUB> are executed when the guard succeeds. In order to choose 
only the right alternative, and not to leave any unwanted choicepoints in the 
execution, we must eliminate the remaining alternatives after the guard succeeds. For 
this we use a cut (!) <A NAME="@default109"></A>after each guard but the last. We can leave out the cut after 
the last guard, as there are no choices left at this point.

<H5 CLASS="paragraph">Parameters</H5>
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>X</B><DD CLASS="dd-description"> a data structure
</DL>

<H5 CLASS="paragraph">Schema</H5>
<PRE CLASS="verbatim">
:-mode alternatives(+).
alternatives(X):-
        q1(X),
        !,
        r1(X).
alternatives(X):-
        q2(X),
        !,
        r2(X).
alternatives(X):-
        qn(X),
        rn(X).
</PRE>
<H5 CLASS="paragraph">Comments</H5>
Very often, other parameters must be passed either to the guards, or to the actions. <BR>
<BR>
The errors which are introduced if a cut to commit to a choice is left out are 
very hard to debug, and may only show after long execution. Much better to 
always cut after each guard.<BR>
<BR>
When adding new parameters it is important to ensure that they are added to all 
clauses of the predicate. If a parameter is not used in some clause, then it 
should be added as a singleton variable.
If we miss an argument on one of the clauses in the middle, the compiler will create an error message about <I>non consecutive clauses</I><A NAME="@default110"></A>. But if we miss an argument for either the first or the last clause, the compiler will just treat this as another predicate definition with the same name, but a different arity. Errors of this form are very hard to spot.

<H5 CLASS="paragraph">Example</H5>
<A NAME="@default111"></A>
<PRE CLASS="verbatim">
:-mode interface_type(+,+,-).
interface_type(_Node,local,local):-
        !.
interface_type(Node,_Interface,backbone_net):-
        node(Node,net),
        !.
interface_type(Node,Interface,backbone):-
        backbone_line(Node,Interface,_,_),
        !.
interface_type(Node,Interface,backbone):-
        backbone_line(_,_,Node,Interface),
        !.
interface_type(Node,Interface,interconnection):-
        group(interconnection,_,Node,Interface),
        !.
interface_type(_Node,_Interface,customer).
</PRE>Here we branch on information passed in the first two arguments, and return a result in the last argument. The last clause is a default rule, saying that the interface type is <I>customer</I>, if none of the other rules applied.<BR>
<BR>
Some programmers perfer to make the output unification explicit, like so:
<PRE CLASS="verbatim">
:-mode interface_type(+,+,-).
interface_type(_Node,local,Result):-
        !,
        Result = local.
interface_type(Node,_Interface,Result):-
        node(Node,net),
        !,
        Result = backbone_net.
interface_type(Node,Interface,Result):-
        backbone_line(Node,Interface,_,_),
        !,
        Result = backbone.
interface_type(Node,Interface,Result):-
        backbone_line(_,_,Node,Interface),
        !,
        Result = backbone.
interface_type(Node,Interface,Result):-
        group(interconnection,_,Node,Interface),
        !,
        Result = interconnection.
interface_type(_Node,_Interface,Result):-
        Result = customer.
</PRE>This has advantages if the predicate may be called with the last argument instantiated.
<A NAME="toc21"></A>
<H2 CLASS="section"><A NAME="htoc45">5.3</A>&nbsp;&nbsp;Iteration on lists</H2>

<H5 CLASS="paragraph">Description</H5>
<A NAME="@default112"></A><A NAME="@default113"></A>This concept is used to perform some action on each element of a list. There are two implementations given here. The first uses the <I>do</I><A NAME="@default114"></A><A NAME="@default115"></A> loop of ECLiPSe, the second uses recursion<A NAME="@default116"></A> to achieve the same purpose. In the <I>do</I> loop, the <I>foreach</I><A NAME="@default117"></A> keyword describes an action for each element of a list. The first argument (here <I>X</I>) is a formal parameter<A NAME="@default118"></A> of the loop. At each iteration, it will be bound to one element of the list. The second argument is the list over which we iterate.<BR>
<BR>
It is a matter of style whether to use the first or second variant. For simple iterations, the <I>do</I> loop is usually more elegant. We can also often use it <I>inline</I><A NAME="@default119"></A>, and avoid introducing a new predicate name just to perform some iteration.

<H5 CLASS="paragraph">Parameters</H5>
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>L</B><DD CLASS="dd-description"> a list
</DL>

<H5 CLASS="paragraph">Schema</H5>
<PRE CLASS="verbatim">
/* version 1 */

:-mode iteration(+).
iteration(L):-
        (foreach(X,L) do
            q(X)
        ).

/* version 2 */

:-mode iteration(+).
iteration([]).
iteration([H|T]):-
        q(H),
        iteration(T).

</PRE>
<H5 CLASS="paragraph">Comments</H5>
If we want to scan several lists in parallel, we can use multiple <I>foreach</I> statements<A NAME="@default120"></A> in the same <I>do</I> loop. The following code fragment calls predicate <I>q</I> for the first elements of list <I>L</I> and <I>K</I>, then for the second elements, etc.
<PRE CLASS="verbatim">
:-mode iteration(+,+).
iteration(L,K):-
        (foreach(X,L),
         foreach(Y,K) do
            q(X,Y)
        ).
</PRE>This requires that the lists are of the same length, otherwise this <I>do</I> loop will fail. <BR>
<BR>
Note that we can put as many parallel operations into a <I>do</I> loop as we want, they are all executed inside one big loop. We can of course also nest <I>do</I> loops so that one loop is executed inside another loop.<BR>
<BR>
The <I>foreach</I> operator can also be used to create a list in a <I>do</I> loop. This is shown in the transformation concept.<BR>
<BR>
Very often, we have to pass additional parameters into the <I>do</I> loop. We do this with the <I>param</I><A NAME="@default121"></A> parameter, which lists all variables from outside the loop that we want to use inside the loop. A variable which is not mentioned as a <I>param</I> argument, is unbound inside the loop. Normally, this will create a warning about a singleton variable<A NAME="@default122"></A> inside a <I>do</I> loop. The following code fragment shows the use of <I>param</I> to pass variables <I>A</I>, <I>B</I> and <I>C</I> to the call of predicate <I>q</I>.
<PRE CLASS="verbatim">
:-mode iteration(+,+,+,+).
iteration(L,A,B,C):-
        (foreach(X,L),
         param(A,B,C) do
            q(X,A,B,C)
        ).
</PRE>
<H5 CLASS="paragraph">Example</H5>
<A NAME="@default123"></A>
<PRE CLASS="verbatim">
% set the group fields inside the interfaces for each interface
:-mode set_group_of_interfaces(+,+).
set_group_of_interfaces(L,Interfaces):-
        (foreach(group with [type:Type,
                             name:Name,
                             interface:I],L),
         param(Interfaces) do
            find_interface(I,Interfaces,Interface),
            set_group_of_interface(Type,Name,Interface)
        ).
</PRE>Here we use the information that each member of the list <I>L</I> is a term <I>group/4</I> <A NAME="@default124"></A>to replace the formal parameter with a term structure where we access individual fields directly. Also note that the body of the loop may contain more than one predicate call.
<A NAME="toc22"></A>
<H2 CLASS="section"><A NAME="htoc46">5.4</A>&nbsp;&nbsp;Iteration on terms</H2>

<H5 CLASS="paragraph">Description</H5>
<A NAME="@default125"></A>We can iterate not only over all elements of a list, as in the previous concept, but also over all arguments of a term. Obviously, this only makes sense if all arguments of the term are of a similar type i.e. the term is used as a <I>vector</I><A NAME="@default126"></A>. The <I>foreacharg</I><A NAME="@default127"></A> keyword of the <I>do</I> loop iterates over each argument of a term.

<H5 CLASS="paragraph">Parameters</H5>
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>T</B><DD CLASS="dd-description"> a term
</DL>

<H5 CLASS="paragraph">Schema</H5>
<PRE CLASS="verbatim">
:-mode iteration(+).
iteration(T):-
        (foreacharg(X,T) do
            q(X)
        ).
</PRE>
<H5 CLASS="paragraph">Comments</H5>
We can use multiple <I>foreacharg</I> keywords to scan multiple vectors at the same time, but we cannot use <I>foreacharg</I> to create terms<A NAME="@default128"></A> (we do not know the functor of the term). If we want to create a new term, we have to generate it with the right functor and arity before the <I>do</I> loop. The following code segment performs vector addition<A NAME="@default129"></A> <I>C</I> = <I>A</I>+ <I>B</I>.
<A NAME="@default130"></A>
<PRE CLASS="verbatim">
:-mode vector_add(+,+,-).
vector_add(A,B,C):-
        functor(A,F,N),
        functor(C,F,N),
        (foreacharg(X,A),
         foreacharg(Y,B),
         foreacharg(Z,C) do
           Z is X + Y
        ).
</PRE>If the terms A and B do not have the same number of arguments, the predicate will fail.

<H5 CLASS="paragraph">Example</H5>
<A NAME="@default131"></A>
<PRE CLASS="verbatim">
:-mode interface_mib_add(+,+,-).
interface_mib_add(A,B,C):-
        C = interface_mib with [],
        (foreacharg(A1,A),
         foreacharg(B1,B),
         foreacharg(C1,C) do
            C1 is A1 + B1
        ).
</PRE>This predicate adds vectors with the functor <I>interface_mib</I> and returns such a vector.
<A NAME="toc23"></A>
<H2 CLASS="section"><A NAME="htoc47">5.5</A>&nbsp;&nbsp;Iteration on array</H2>
<A NAME="iterationonarray"></A>

<H5 CLASS="paragraph">Description</H5>
<A NAME="@default132"></A>The next concept is iteration on an array <A NAME="@default133"></A>structure. We often want to perform some action on each element of a two-dimensional array. <BR>
<BR>
Again, we present two implementations. The first uses nested <I>foreacharg</I><A NAME="@default134"></A> <I>do</I> loops to perform some operation <I>q</I> on each element of an array. The second uses nested <I>for</I><A NAME="@default135"></A><A NAME="@default136"></A> loops to iterate over all index combinations <I>I</I> and <I>J</I>. This second variant is more complex, and should be used only if we require the index values <I>I</I> and <I>J</I> as well as the matrix element <I>X</I>. 

<H5 CLASS="paragraph">Parameters</H5>
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>Matrix</B><DD CLASS="dd-description"> a matrix
</DL>

<H5 CLASS="paragraph">Schema</H5>
<PRE CLASS="verbatim">
/* version 1 */

:-mode iteration(+).
iteration(Matrix):-
        (foreacharg(Line,Matrix) do
            (foreacharg(X,Line) do
                q(X)
            )
        ).

/* version 2 */

:-mode iteration(+).
iteration(Matrix):-
        dim(Matrix,[N,M]),
        (for(I,1,N),
         param(M,Matrix) do
            (for(J,1,M),
             param(I,Matrix) do
                subscript(Matrix,[I,J],X),
                q(X,I,J)
            )
        ).
</PRE>
<H5 CLASS="paragraph">Comments</H5>
The <I>dim</I><A NAME="@default137"></A> predicate can not only be used to create arrays, but also to find the size of an existing array. <BR>
<BR>
Note the strange way in which parameters <I>M</I>, <I>I</I> and <I>Matrix</I> are passed through the nested <I>for</I> loops with <I>param</I> arguments. But if we do not do this, then the variable <I>Matrix</I> outside and inside the <I>do</I> loop are unrelated.

<H5 CLASS="paragraph">Example</H5>
The example calls the predicate <I>fill_empty/3</I> for each index combination of entries in a matrix <I>PMatrix</I>.
<A NAME="@default138"></A>
<PRE CLASS="verbatim">
:-mode fill_rest_with_empty(+,+).
fill_rest_with_empty(N,PMatrix):-
        (for(I,1,N),
         param(PMatrix,N) do
            (for(J,1,N),
             param(PMatrix,I) do
                fill_empty(PMatrix,I,J)
            )
        ).
</PRE>
<A NAME="toc24"></A>
<H2 CLASS="section"><A NAME="htoc48">5.6</A>&nbsp;&nbsp;Transformation</H2>

<H5 CLASS="paragraph">Description</H5>
This next concept is used to perform some transformation<A NAME="@default139"></A> on each element of a list and to create a list of the transformed elements. At the end, both lists will have the same length, and the elements match, i.e. the first element of the second list is the transformed first element of the first list. <BR>
<BR>
This concept uses the <I>foreach</I><A NAME="@default140"></A> keyword in two different ways. The first is used to scan an existing list <I>L</I>, the second is used to construct a list<A NAME="@default141"></A> <I>K</I> as the result of the operation.

<H5 CLASS="paragraph">Parameters</H5>
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>L</B><DD CLASS="dd-description"> a list
<DT CLASS="dt-description"><B>K</B><DD CLASS="dd-description"> a free variable, will be bound to a list
</DL>

<H5 CLASS="paragraph">Schema</H5>
<PRE CLASS="verbatim">
:-mode transformation(+,-).
transformation(L,K):-
        (foreach(X,L),
         foreach(Y,K) do
            q(X,Y)
        ).
</PRE>
<H5 CLASS="paragraph">Comments</H5>
In the code above we cannot see that list <I>L</I> is an input and list <I>K</I> is an output. This can only be deduced from the calling pattern or from the mode declaration<A NAME="@default142"></A>. <BR>
<BR>

<H5 CLASS="paragraph">Example</H5>
The example takes a list of <I>router_mib_data</I> terms and builds a list of temporary <I>t/2</I> terms where the second argument consists of <I>router_mib</I> terms.
<A NAME="@default143"></A>
<PRE CLASS="verbatim">
:-mode convert_to_router_mib(+,-,-).
convert_to_router_mib(L,K,Router):-
        (foreach(router_mib_data with 
                 [router:Router,
                  time:Time,
                  tcp_segm_in:A,
                  tcp_segm_out:B,
                  udp_datagram_in:C,
                  udp_datagram_out:D],L),
         foreach(t(Time,router_mib with 
                   [tcp_segm_in:A,
                   tcp_segm_out:B,
                   udp_datagram_in:C,
                   udp_datagram_out:D]),K),
         param(Router) do
            true
         ).
</PRE>In this example the transformation is completely handled by matching arguments in the <I>foreach</I> statements. We use the predicate <I>true</I> <A NAME="@default144"></A>for an empty loop body<A NAME="@default145"></A>.<BR>
<BR>
Figuring out what is happening with the variable <I>Router</I> is left as an exercise for the advanced reader.
<A NAME="toc25"></A>
<H2 CLASS="section"><A NAME="htoc49">5.7</A>&nbsp;&nbsp;Filter</H2>

<H5 CLASS="paragraph">Description</H5>
The filter<A NAME="@default146"></A> concept extracts from a list of elements those that satisfy some condition <I>q</I> and returns a list of these elements.<BR>
<BR>
We present three implementations, one using recursion, the others using a <I>do</I> loop with the <I>fromto</I><A NAME="@default147"></A> keyword.

<H5 CLASS="paragraph">Parameters</H5>
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>L</B><DD CLASS="dd-description"> a list
<DT CLASS="dt-description"><B>K</B><DD CLASS="dd-description"> a free variable, will be bound to a list
</DL>

<H5 CLASS="paragraph">Schema</H5>
<PRE CLASS="verbatim">
/* version 1 */

:-mode filter(+,-).
filter([],[]).
filter([A|A1],[A|B1]):-
        q(A),
        !,
        filter(A1,B1).
filter([_A|A1],B1):-
        filter(A1,B1).

/* version 2 */

:-mode filter(+,-).
filter(L,K):-
        (foreach(X,L),
         fromto([],In,Out,K) do
            q(X,In,Out)
        ).

q(X,L,[X|L]):-
        q(X),
        !.
q(_,L,L).
</PRE><PRE CLASS="verbatim">
/* version 3 */

:-mode filter(+,-).
filter(L,K):-
        (foreach(X,L),
         fromto(K,In,Out,[]) do
            q(X,In,Out)
        ).

q(X,[X|L],L):-
        q(X),
        !.
q(_,L,L).
</PRE>
<H5 CLASS="paragraph">Comments</H5>
The difference between versions 2 and 3 lies in the order of the elements in the result list. Version 2 produces the elements in the inverse order of version 1, whereas version 3 produces them in the same order as version 1. This shows that the <I>fromto</I> statement can be used to build lists forwards or backwards. Please note that the predicate <I>q/3</I> is also different in variants 2 and 3.<BR>
<BR>
The cuts (!) <A NAME="@default148"></A>in the program clauses are very important, as they remove the possibility that a selected element is not included in the filtered list. If we remove the cuts, then the <I>filter</I> predicate has an exponential number of &#8220;solutions&#8221;. Only the first solution will be correct, on backtracking we will decide to reject elements which satisfy the test criterion and we will explore all combinations until we reach the empty list as the last &#8220;solution&#8221;.

<H5 CLASS="paragraph">Example</H5>
The following program is used to extract interfaces related to customers (types customer, selected and remaining) as a list of <I>customer/3</I> terms, group them by node and perform some action on each group.
<A NAME="@default149"></A>
<A NAME="@default150"></A>
<PRE CLASS="verbatim">
:-mode selected_min_max(+,+).
selected_min_max(Type,Interfaces):-
        Interfaces = interfaces with list:List,
        (foreach(Interface,List),
         fromto([],In,Out,Customers) do
            selected_customer(Interface,In,Out)
        ),
        sort(0,=&lt;,Customers,Sorted),
        customers_by_node(Sorted,Grouped),
        selected_together(Type,Grouped,Interfaces).

selected_customer(interface with [type:Type,
                                  index:I,
                                  node_index:Node],
                  In,
                  [customer with [node:Node,
                                  index:I,
                                  type:Type]|In]):-
        memberchk(Type,[customer,selected,remaining]),
        !.
% all other types: backbone,backbone_net,interconnection,local
selected_customer(_,In,In).
</PRE>
<A NAME="toc26"></A>
<H2 CLASS="section"><A NAME="htoc50">5.8</A>&nbsp;&nbsp;Combine</H2>

<H5 CLASS="paragraph">Description</H5>
This concept takes a list, combines<A NAME="@default151"></A> consecutive elements according to some criterion and returns a list of the combined elements.<BR>
<BR>
The typical use of this concept will first sort the input list so that elements that can be combined are consecutive in the list.

<H5 CLASS="paragraph">Parameters</H5>
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>L</B><DD CLASS="dd-description"> a list
<DT CLASS="dt-description"><B>Res</B><DD CLASS="dd-description"> a free variable, will be bound to a list
</DL>

<H5 CLASS="paragraph">Schema</H5>
<PRE CLASS="verbatim">
:-mode combine(+,-).
combine([],[]).
combine([A,B|R],Res):-
        can_combine(A,B,C),
        !,
        combine([C|R],Res).
combine([A|A1],[A|Res]):-
        combine(A1,Res).
</PRE>
<H5 CLASS="paragraph">Comments</H5>
It is important to note that the recursive call in the second clause continues with the combined element <I>C</I>, since it may be combined with more elements of the rest of the list <I>R</I>.<BR>
<BR>
The cut in the second clause ensures that elements that can be combined are always combined, and that we do not leave a choice point in the execution.<BR>
<BR>
The most simple use of the concept is the removal of duplicate entries<A NAME="@default152"></A> in a sorted list.<BR>
<BR>

<H5 CLASS="paragraph">Example</H5>
<A NAME="@default153"></A>
<A NAME="@default154"></A>
<PRE CLASS="verbatim">
:-mode combine_traffic(+,-).
combine_traffic([],[]).
combine_traffic([A,B|R],L):-
        try_to_combine(A,B,C),
        !,
        combine_traffic([C|R],L).
combine_traffic([A|R],[A|S]):-
        combine_traffic(R,S).

try_to_combine(interface_traffic_sample(Time,Router,Interface,
                                        X1,X2,X3,X4,X5,
                                        X6,X7,X8,X9,X10),
        interface_traffic_sample(Time,Router,Interface,
                                 Y1,Y2,Y3,Y4,Y5,
                                 Y6,Y7,Y8,Y9,Y10),
        interface_traffic_sample(Time,Router,Interface,
                                 Z1,Z2,Z3,Z4,Z5,
                                 Z6,Z7,Z8,Z9,Z10)):-
        Z1 is X1+Y1,
        Z2 is X2+Y2,
        Z3 is X3+Y3,
        Z4 is X4+Y4,
        Z5 is X5+Y5,
        Z6 is X6+Y6,
        Z7 is X7+Y7,
        Z8 is X8+Y8,
        Z9 is X9+Y9,
        Z10 is X10+Y10.
</PRE>Here we combine traffic samples for the same interface and time point by adding the sample values <I>X</I><SUB>1</SUB> ... <I>X</I><SUB>10</SUB> and <I>Y</I><SUB>1</SUB> ... <I>Y</I><SUB>10</SUB>. The predicate <I>try_to_combine</I> will only succeed if the two input arguments have the same time stamp, router and interface, but it will fail if the arguments differ on these fields. <BR>
<BR>
Also note that we do not use named structures in this example. This is justified as any extension of the structure would probably entail a change of the program anyway.
<A NAME="toc27"></A>
<H2 CLASS="section"><A NAME="htoc51">5.9</A>&nbsp;&nbsp;Minimum</H2>

<H5 CLASS="paragraph">Description</H5>
<A NAME="@default155"></A>This concept selects the smallest element of a list according to some comparison operator <I>better</I>.

<H5 CLASS="paragraph">Parameters</H5>
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>L</B><DD CLASS="dd-description"> a list
<DT CLASS="dt-description"><B>V</B><DD CLASS="dd-description"> a free variable, will be bound to an entry of <I>L</I>
</DL>

<H5 CLASS="paragraph">Schema</H5>
<PRE CLASS="verbatim">
:-mode minimum(+,-).
minimum([H|T],V):-
        (foreach(X,T),
         fromto(H,In,Out,V) do
            minimum_step(X,In,Out)
        ).

minimum_step(X,Old,X):-
        better(X,Old),
        !.
minimum_step(X,Old,Old).
</PRE>
<H5 CLASS="paragraph">Comments</H5>
This implementation of minimum fails if the input list has no elements. This means that somewhere else in the program we have to handle the case where the input list is empty. This seems to be the most clear definition of minimum, an empty list does not have a smallest element.<BR>
<BR>
If several elements of the list have the same minimal value, only the first one is returned.
<A NAME="toc28"></A>
<H2 CLASS="section"><A NAME="htoc52">5.10</A>&nbsp;&nbsp;Best and rest</H2>

<H5 CLASS="paragraph">Description</H5>
<A NAME="@default156"></A>This concept is an extension of the minimum concept. It not only returns the best element in the input list, but also the rest of the original list without the best element. This rest can then be used for example to select another element, and so on.

<H5 CLASS="paragraph">Parameters</H5>
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>L</B><DD CLASS="dd-description"> a list
<DT CLASS="dt-description"><B>Best</B><DD CLASS="dd-description"> a free variable, will be bound to an entry of <I>L</I>
<DT CLASS="dt-description"><B>Rest</B><DD CLASS="dd-description"> a free variable, will be bound to a list of the entries of <I>L</I> without <I>Best</I>
</DL>

<H5 CLASS="paragraph">Schema</H5>
<PRE CLASS="verbatim">
:-mode best_and_rest(+,-,-).
best_and_rest([H|T],Best,Rest):-
        (foreach(X,T),
         fromto(H,In1,Out1,Best),
         fromto([],In2,Out2,Rest) do
            best(X,In1,Out1,In2,Out2)
        ).

best(X,Y,X,L,[Y|L]):-
        better(X,Y),
        !.
best(X,Y,Y,L,[X|L]).
</PRE>
<H5 CLASS="paragraph">Comments</H5>
The predicate fails if the input list is empty. We must handle that case somewhere else in the program.<BR>
<BR>
If several elements of the list have the same best value, only the first one is selected. <BR>
<BR>
The order of elements in <I>Rest</I> may be quite different from the order in the input list. If that is not acceptable, we must use a different implementation. A rather clever one is given below:
<PRE CLASS="verbatim">
best_and_rest([First|Xs],Best,Rest):-
        (foreach(X,Xs),
         fromto(First,BestSoFar,NextBest,Best),
         fromto(Start,Rest1,Rest2,[]),
         fromto(Start,Head1,Head2,Gap),
         fromto(Rest,Tail1,Tail2,Gap) do
            (better(X,BestSoFar) -&gt;
                NextBest = X,
                Tail1 = [BestSoFar|Head1],
                Tail2 = Rest1,
                Head2 = Rest2
            ;
                NextBest = BestSoFar,
                Tail2 = Tail1,
                Head2 = Head1,
                Rest1 = [X|Rest2]
            )
        ).
</PRE><A NAME="toc29"></A>
<H2 CLASS="section"><A NAME="htoc53">5.11</A>&nbsp;&nbsp;Sum</H2>

<H5 CLASS="paragraph">Description</H5>
The sum <A NAME="@default157"></A>concept returns the sum of values which have been extracted from a list of data structures. It uses a <I>foreach</I> to scan each elements of the list and a <I>fromto</I> to accumulate the total sum.

<H5 CLASS="paragraph">Parameters</H5>
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>L</B><DD CLASS="dd-description"> a list
<DT CLASS="dt-description"><B>Sum</B><DD CLASS="dd-description"> a free variable, will be bound to a value
</DL>

<H5 CLASS="paragraph">Schema</H5>
<PRE CLASS="verbatim">
:-mode sum(+,-).
sum(L,Sum):-
        (foreach(X,L),
         fromto(0,In,Out,Sum) do
            q(X,V),
            Out is In+V
        ).
</PRE>
<H5 CLASS="paragraph">Comments</H5>
The initial value<A NAME="@default158"></A> for the sum accumulator here is 0. We could use another initial value, this can be useful if we want to obtain the total over several summations. 

<H5 CLASS="paragraph">Example</H5>
The program counts how many entries in the <I>interface_mib_data</I> list refer to active interfaces (octet count non-zero).
<A NAME="@default159"></A>
<PRE CLASS="verbatim">
:-mode non_zero_measurements(+,-).
non_zero_measurements(L,N):-
        (foreach(X,L),
         fromto(0,In,Out,N) do
            non_zero_measurement(X,In,Out)
        ).

non_zero_measurement(interface_mib_data with [octet_in:A,
                                              octet_out:B],
                     In,Out):-
        A+B &gt; 0,
        !,
        Out is In+1.
non_zero_measurement(_X,In,In).
</PRE><A NAME="toc30"></A>
<H2 CLASS="section"><A NAME="htoc54">5.12</A>&nbsp;&nbsp;Merge</H2>

<H5 CLASS="paragraph">Description</H5>
The merge <A NAME="@default160"></A>concept is used when we want to match corresponding entries in two lists. We sort both lists on the same key, and then scan them in parallel, always discarding the entry with the smallest key first.<BR>
<BR>
We can use this concept to combine information from the two lists, to find differences between lists <A NAME="@default161"></A>quickly, or to lookup <A NAME="@default162"></A>information from the second list for all elements of the first list.

<H5 CLASS="paragraph">Parameters</H5>
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>L</B><DD CLASS="dd-description"> a list
<DT CLASS="dt-description"><B>K</B><DD CLASS="dd-description"> a list
</DL>

<H5 CLASS="paragraph">Schema</H5>
<PRE CLASS="verbatim">
:-mode merge(+,+).
merge(L,K):-
        sort_on_key(L,L1),
        sort_on_key(K,K1),
        merge_lp(L1,K1).

merge_lp([],_):-
        !.
merge_lp([_|_],[]):-
        !.
merge_lp([A|A1],[B|B1]):-
        merge_compare(A,B,Op),
        merge_cont(Op,A,A1,B,B1).

merge_cont(&lt;,A,A1,B,B1):-
        merge_lp(A1,[B|B1]).
merge_cont(=,A,A1,B,B1):-
        merge_op(A,B),
        merge_lp(A1,[B|B1]).
merge_cont(&gt;,A,A1,B,B1):-
        merge_lp([A|A1],B1).
</PRE>
<H5 CLASS="paragraph">Comments</H5>
The cuts in <I>merge_lp</I> are used to remove choicepoints<A NAME="@default163"></A> left by the compiler<SUP><A NAME="text7" HREF="#note7">1</A></SUP>.<BR>
<BR>
The schema looks quite complex, but its performance is nearly always significantly better than a simple lookup in the second list.

<H5 CLASS="paragraph">Example</H5>
The example takes data from two different sources and merges it. The first argument is a list of <I>interface_topology</I> terms, the second a list of <I>ndi_interface</I> structures. For matching <I>Node</I>&minus;<I>Interface</I> pairs, we copy information from the first structure into the second. If the <I>Node</I>&minus;<I>Interface</I> pairs do not match, then we don't do anything.<BR>
<BR>
Also note the use of <I>compare/3</I> to obtain a lexicographical ordering of <I>Node</I>&minus;<I>Interface</I> pairs.<BR>
<BR>
<A NAME="@default164"></A>
<A NAME="@default165"></A>
<A NAME="@default166"></A>
<PRE CLASS="verbatim">
:-mode insert_topology(+,+).
insert_topology([],_):-
        !.
insert_topology([_|_],[]):-
        !.
insert_topology([A|A1],[B|B1]):-
        compare_index_interface(A,B,Op),
        insert_topology_op(Op,A,B,A1,B1).

compare_index_interface(interface_topology(_,Router1,
                                           Index1,_,_),
                  ndi_interface with [router:Router2,
                                      index:Index2],Op):-
        compare(Op,Router1-Index1,Router2-Index2).

insert_topology_op(&lt;,A,B,A1,B1):-
        insert_topology(A1,[B|B1]).
insert_topology_op(=,A,B,A1,B1):-
        insert_one_topology(A,B),
        insert_topology(A1,B1).
insert_topology_op(&gt;,A,_B,A1,B1):-
        insert_topology([A|A1],B1).

insert_one_topology(interface_topology(_,_,_,Ip,Mask),
                    ndi_interface with [ip_address:Ip,
                                    subnet_mask:Mask,
                                    subnet:Subnet]):-
        subnet(Ip,Mask,Subnet).        
</PRE>
<A NAME="toc31"></A>
<H2 CLASS="section"><A NAME="htoc55">5.13</A>&nbsp;&nbsp;Group</H2>

<H5 CLASS="paragraph">Description</H5>
<A NAME="@default167"></A>This concept takes a sorted list of items and creates a list of lists, where items with the same key are put in the same sub-list. This works even for the empty input list.<BR>
<BR>
The second argument of <I>group_lp</I> serves as an accumulator<A NAME="@default168"></A> to collect items with the same key. As long as the next item uses the same key, it is put into this accumulator (2nd clause). If the remaining list is empty (1st clause) or it starts with an element of a different key (3rd clause), the accumulated list is put into the output list.

<H5 CLASS="paragraph">Parameters</H5>
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>L</B><DD CLASS="dd-description"> a list
<DT CLASS="dt-description"><B>K</B><DD CLASS="dd-description"> a free variable, will be bound to a list
</DL>

<H5 CLASS="paragraph">Schema</H5>
<PRE CLASS="verbatim">
:-mode group(+,-).
group([],[]).
group([H|T],K):-
        group_lp(T,[H],K).

group_lp([],L,[L]).
group_lp([H|T],[A|A1],K):-
        same_group(H,A),
        !,
        group_lp(T,[H,A|A1],K).
group_lp([H|T],L,[L|K]):-
        group_lp(T,[H],K).
</PRE>
<H5 CLASS="paragraph">Comments</H5>
The order of items in the resulting sub lists is the reverse of their order in the initial list.<BR>
<BR>
The order of the sub lists in the result is the same as the order of the keys in the original list.<BR>
<BR>
If the initial list is not sorted by the same key that is used in <I>same_group</I>, then this program does not work at all.

<H5 CLASS="paragraph">Example</H5>
The following program takes a list of terms and groups them according to some argument number <I>N</I>. It returns a list of <I>group/2</I> terms, where the first argument is the common key in the group, and the second argument is a list of all terms which share that key.
<A NAME="@default169"></A>
<PRE CLASS="verbatim">
:-mode group(+,+,-).
group([],_,[]):-
        !.
group(Terms,N,Grouped):-
        sort(N,=&lt;,Terms,[H|T]),
        arg(N,H,Group),
        group1(T,Group,[H],N,Grouped).

group1([],Group,L,_,[group(Group,L)]).
group1([H|T],Group,L,N,Grouped):-
        arg(N,H,Group),
        !,
        group1(T,Group,[H|L],N,Grouped).
group1([H|T],Old,L,N,[group(Old,L)|Grouped]):-
        arg(N,H,Group),
        group1(T,Group,[H],N,Grouped).
</PRE>
<A NAME="toc32"></A>
<H2 CLASS="section"><A NAME="htoc56">5.14</A>&nbsp;&nbsp;Lookup</H2>

<H5 CLASS="paragraph">Description</H5>
The lookup <A NAME="@default170"></A>concept is used to convert data stored in the local database into a list of terms that can be manipulated in the program. The most natural template (first argument of <I>findall</I>)<A NAME="@default171"></A> is to use the same term as for the facts<A NAME="@default172"></A> in the database.

<H5 CLASS="paragraph">Parameters</H5>
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>Res</B><DD CLASS="dd-description"> a free variable, will be bound to a list
</DL>

<H5 CLASS="paragraph">Schema</H5>
<PRE CLASS="verbatim">
:-mode lookup(-).
lookup(Res):-
        findall(q(X),q(X),Res).
</PRE>
<H5 CLASS="paragraph">Comments</H5>
<I>findall</I> examplifies a typical <I>meta-predicate</I><A NAME="@default173"></A>, the second argument is actually a goal that will be executed. There are a number of other predicates of this type, and this feature can be extremely useful in writing interpreters, emulators etc, which treat data as program parts.<BR>
<BR>
The <I>findall</I> predicate is significantly faster than <I>bagof</I><A NAME="@default174"></A> or <I>setof</I><A NAME="@default175"></A>. Their use is not recommended. 

<H5 CLASS="paragraph">Example</H5>
<A NAME="@default176"></A>
<PRE CLASS="verbatim">
% find all hops routing information
:-mode gather_hops(-).
gather_hops(Hops):-
        findall(hop(A,B,C),hop(A,B,C),Hops).
</PRE>
<A NAME="toc33"></A>
<H2 CLASS="section"><A NAME="htoc57">5.15</A>&nbsp;&nbsp;Fill matrix</H2>

<H5 CLASS="paragraph">Description</H5>
<A NAME="@default177"></A>
<A NAME="@default178"></A>
This concept takes a list of entries with indices <I>I</I> and <I>J</I> and a value <I>V</I>, and put the value in a matrix <I>M</I> at position <I>M</I><SUB><I>i</I>,<I>j</I></SUB>.

<H5 CLASS="paragraph">Parameters</H5>
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>L</B><DD CLASS="dd-description"> a list of entries
<DT CLASS="dt-description"><B>Matrix</B><DD CLASS="dd-description"> a matrix
</DL>

<H5 CLASS="paragraph">Schema</H5>
<PRE CLASS="verbatim">
:-mode fill_matrix(+,+).
fill_matrix(L,Matrix):-
        (foreach(entry with [i:I,j:J,value:V],L),
         param(Matrix) do
            subscript(Matrix,[I,J],V)
        ).
</PRE>
<H5 CLASS="paragraph">Comments</H5>
The program may fail if two entries in the list refer to the same index pair <I>I</I> and <I>J</I>, as the program would then try to insert two values at the same position.<BR>
<BR>
It is not required that the input list contains all index combinations, we can use the <I>iteration on array</I> concept to fill any un-set elements with a default value.

<H5 CLASS="paragraph">Example</H5>
The example fills an array <I>PMatrix</I> with values from a list of <I>hop/3</I> terms. We also convert the node names in the <I>hop</I> term into node indices for lookup in the <I>PMatrix</I> matrix.
<A NAME="@default179"></A>
<PRE CLASS="verbatim">
:-mode fill_with_hops(+,+,+).
fill_with_hops([],_,_).
fill_with_hops([hop(Source,Dest,List)|R],Nodes,PMatrix):-
        find_node_index(Source,Nodes,S),
        find_node_index(Dest,Nodes,D),
        find_node_indices(List,Nodes,L),
        length(L,N), 
        subscript(PMatrix,[S,D],pi_entry with [list:L,
                                               length:N]),
        fill_with_hops(R,Nodes,PMatrix).
</PRE>
<A NAME="toc34"></A>
<H2 CLASS="section"><A NAME="htoc58">5.16</A>&nbsp;&nbsp;Cartesian</H2>

<H5 CLASS="paragraph">Description</H5>
<A NAME="@default180"></A>This concept takes two input lists <I>L</I> and <I>K</I> and creates a list of pairs <I>Res</I>, in which each combination of elements of the first and the second list occurs exactly once.<BR>
<BR>
The result is a list of terms <I>pair(X, Y)</I>, where <I>X</I> is an element of list <I>L</I> and <I>Y</I> is an element of list <I>K</I>.<BR>
<BR>
The implementation uses nested <I>foreach</I> <I>do</I> loops to create each combination of elements once. The <I>fromto</I> accumulators are used to collect the result list.

<H5 CLASS="paragraph">Parameters</H5>
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>L</B><DD CLASS="dd-description"> a list
<DT CLASS="dt-description"><B>K</B><DD CLASS="dd-description"> a list
<DT CLASS="dt-description"><B>Res</B><DD CLASS="dd-description"> a free variable, will be bound to a list
</DL>

<H5 CLASS="paragraph">Schema</H5>
<PRE CLASS="verbatim">
:-mode cartesian(+,+,-).
cartesian(L,K,Res):-
        (foreach(X,L),
         fromto([],In,Out,Res),
         param(K) do
            (foreach(Y,K),
             fromto(In,In1,[pair(X,Y)|In1],Out),
             param(X) do
                true
            )
        ).
</PRE>
<H5 CLASS="paragraph">Comments</H5>
Note the use of an empty body (<I>true</I>) <A NAME="@default181"></A>in the innermost loop. All calculations are done by parameter passing alone.<BR>
<BR>
If we want to create the elements in the same order as the elements in the input list, we have to exchange input and output arguments of the <I>fromto</I> statements, like so:
<PRE CLASS="verbatim">
:-mode cartesian(+,+,-).
cartesian(L,K,Res):-
        (foreach(X,L),
         fromto(Res,In,Out,[]),
         param(K) do
            (foreach(Y,K),
             fromto(In,[pair(X,Y)|In1],In1,Out),
             param(X) do
                true
            )
        ).
</PRE>
<H5 CLASS="paragraph">Example</H5>
The example builds all pairs of sources and sink nodes for flows and creates contribution structures from them. An additional accumulator <I>NoPath</I> is used to collect cases where there is no route between the nodes.
<A NAME="@default182"></A>
<PRE CLASS="verbatim">
:-mode create_contribution(+,+,+,-,-).
create_contribution(FromList,ToList,
                    PMatrix,Contribution,NoPath):-
        (foreach(From,FromList),
         fromto([],In1,Out1,Contribution),
         fromto([],NP1,NP2,NoPath),
         param(ToList,PMatrix) do
            (foreach(To,ToList),
             fromto(In1,In,Out,Out1),
             fromto(NP1,NoPath1,NoPath2,NP2),
             param(From,PMatrix) do
                contribution(From,To,From,To,1,PMatrix,
                             In,Out,NoPath1,NoPath2)
            )
        ).
</PRE>
<A NAME="toc35"></A>
<H2 CLASS="section"><A NAME="htoc59">5.17</A>&nbsp;&nbsp;Ordered pairs</H2>

<H5 CLASS="paragraph">Description</H5>
This concept creates ordered pairs<A NAME="@default183"></A><A NAME="@default184"></A> of entries from a list. Each combination where the first element occurs in the input list before the second element is created exactly once.<BR>
<BR>
The result is a list of terms <I>pair(X, Y)</I> where <I>X</I> and <I>Y</I> are elements of the input list <I>L</I>.

<H5 CLASS="paragraph">Parameters</H5>
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>L</B><DD CLASS="dd-description"> a list
<DT CLASS="dt-description"><B>K</B><DD CLASS="dd-description"> a free variable, will be bound to a list
</DL>

<H5 CLASS="paragraph">Schema</H5>
<PRE CLASS="verbatim">
:-mode ordered_pairs(+,-).
ordered_pairs(L,K):-
        ordered_pairs_lp(L,[],K).

ordered_pairs_lp([],L,L).
ordered_pairs_lp([H|T],In,Out):-
        ordered_pairs_lp2(H,T,In,In1),
        ordered_pairs_lp(T,In1,Out).

ordered_pairs_lp2(H,[],L,L).
ordered_pairs_lp2(H,[A|A1],In,Out):-
        ordered_pairs_lp2(H,A1,[pair(H,A)|In],Out).
</PRE>
<H5 CLASS="paragraph">Comments</H5>
The second and third argument of <I>ordered_pairs_lp</I> and the third and fourth argument of <I>ordered_pairs_lp2</I> serve as an accumulator to collect the results.<BR>
<BR>
This concept can also be implemented with nested <I>do</I> loops. The recursive version seems more natural.
<PRE CLASS="verbatim">
ordered_pairs(L,K):-
        (fromto(L,[El|Rest],Rest,[_]),
         fromto(K,TPairs,RPairs,[]) do
            (foreach(R,Rest),
             param(El),
             fromto(TPairs,[pair(El,R)|Pairs],Pairs,RPairs) do
                true
            )
        ).
</PRE><HR WIDTH="50%" SIZE=1><DL CLASS="list"><DT CLASS="dt-list"><A NAME="note7" HREF="#text7"><FONT SIZE=5>1</FONT></A><DD CLASS="dd-list">As ECLiPSe only uses indexing on a single argument, the compiler cannot recognize that the clause patterns are exclusive.
</DL>
<HR>
<A HREF="tutorial005.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial007.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
